home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / scfe.c < prev    next >
C/C++ Source or Header  |  1997-03-21  |  15KB  |  501 lines
  1. /* Copyright (C) 1992, 1995, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* scfe.c */
  20. /* CCITTFax encoding filter */
  21. #include "stdio_.h"    /* includes std.h */
  22. #include "memory_.h"
  23. #include "gdebug.h"
  24. #include "strimpl.h"
  25. #include "scf.h"
  26. #include "scfx.h"
  27.  
  28. /* ------ Macros and support routines ------ */
  29.  
  30. /* Statistics */
  31.  
  32. #ifdef DEBUG
  33. private struct _r1d { ulong termination[64], make_up[41]; } runs_1d[2];
  34. #  define count_run(tab, i) ((tab)[i]++)
  35. #else
  36. #  define count_run(cnt, n) DO_NOTHING
  37. #endif
  38.  
  39. /* Put a run onto the output stream. */
  40. /* Free variables: q, wlimit, status. */
  41.  
  42. #define cf_ensure_put_runs(max_bytes, color, out)\
  43.     if ( wlimit - q < ss->max_bytes )    /* worst case */\
  44.     {    ss->run_color = color;\
  45.         status = 1;\
  46.         goto out;\
  47.     }
  48. #define cf_put_run(ss, lenv, tt, mut, tab)\
  49. {    cfe_run rr;\
  50.     if ( lenv >= 64 )\
  51.     {    while ( lenv >= 2560 + 64 )\
  52.           {    rr = mut[40];\
  53.             count_run(tab.make_up, 40);\
  54.             hc_put_value(ss, q, rr.code, rr.code_length);\
  55.             lenv -= 2560;\
  56.           }\
  57.         rr = mut[lenv >> 6];\
  58.         count_run(tab.make_up, lenv >> 6);\
  59.         hc_put_value(ss, q, rr.code, rr.code_length);\
  60.         lenv &= 63;\
  61.     }\
  62.     rr = tt[lenv];\
  63.     count_run(tab.termination, lenv);\
  64.     hc_put_value(ss, q, rr.code, rr.code_length);\
  65. }
  66.  
  67. #define cf_put_white_run(ss, lenv)\
  68.   cf_put_run(ss, lenv, cf_white_termination, cf_white_make_up, runs_1d[0])
  69.  
  70. #define cf_put_black_run(ss, lenv)\
  71.   cf_put_run(ss, lenv, cf_black_termination, cf_black_make_up, runs_1d[1])
  72.  
  73. /* ------ CCITTFaxEncode ------ */
  74.  
  75. private_st_CFE_state();
  76.       
  77. #define ss ((stream_CFE_state *)st)
  78.  
  79. private void s_CFE_release(P1(stream_state *));
  80.  
  81. /*
  82.  * For the 2-D encoding modes, we leave the previous complete scan line
  83.  * at the beginning of the buffer, and start the new data after it.
  84.  */
  85.  
  86. /* Set default parameter values. */
  87. private void
  88. s_CFE_set_defaults(register stream_state *st)
  89. {    s_CFE_set_defaults_inline(ss);
  90. }
  91.  
  92. /* Initialize CCITTFaxEncode filter */
  93. private int
  94. s_CFE_init(register stream_state *st)
  95. {    int columns = ss->Columns;
  96.     int raster = ss->raster =
  97.       round_up((columns + 7) >> 3, ss->DecodedByteAlign);
  98.  
  99.     s_hce_init_inline(ss);
  100.     ss->count = raster << 3;    /* starting a scan line */
  101.     ss->lbuf = ss->lprev = 0;
  102.     if ( columns > cfe_max_width )
  103.       return ERRC;            /****** WRONG ******/
  104.     /* Because skip_white_pixels can look as many as 4 bytes ahead, */
  105.     /* we need to allow 4 extra bytes at the end of the row buffers. */
  106.     ss->lbuf = gs_alloc_bytes(st->memory, raster + 4,
  107.                   "CFE lbuf");
  108.     if ( ss->lbuf == 0 )
  109.       {    s_CFE_release(st);
  110.         return ERRC;        /****** WRONG ******/
  111.       }
  112.     if ( ss->K != 0 )
  113.     {    ss->lprev = gs_alloc_bytes(st->memory, raster + 4,
  114.                        "CFE lprev");
  115.         if ( ss->lprev == 0 )
  116.           {    s_CFE_release(st);
  117.             return ERRC;        /****** WRONG ******/
  118.           }
  119.         /* Clear the initial reference line for 2-D encoding. */
  120.         /* Make sure it is terminated properly. */
  121.         memset(ss->lprev, (ss->BlackIs1 ? 0 : 0xff), raster);
  122.         if ( columns & 7 )
  123.           ss->lprev[raster - 1] ^= 0x80 >> (columns & 7);
  124.         else
  125.           ss->lprev[raster] = ~ss->lprev[0];
  126.     }
  127.     ss->copy_count = raster;
  128.     ss->new_line = true;
  129.     ss->k_left = (ss->K > 0 ? 1 : ss->K);
  130.     /* Initialize values for buffer space checking. */
  131.     { int max_bytes = cfe_max_code_bytes(columns);
  132.  
  133.       /*
  134.        * For a single-run line, we need room for byte alignment,
  135.        * an aligned EOL, run_horizontal, and 2 runs.
  136.        */
  137.       ss->max_line_bytes = max_bytes * 2 + 4;
  138.       ss->max_run2_bytes = max_bytes * 2;
  139.       ss->max_run3_bytes = max_bytes * 3;
  140.     }
  141.     return 0;
  142. }
  143.  
  144. /* Release the filter. */
  145. private void
  146. s_CFE_release(stream_state *st)
  147. {    gs_free_object(st->memory, ss->lprev, "CFE lprev(close)");
  148.     gs_free_object(st->memory, ss->lbuf, "CFE lbuf(close)");
  149. }
  150.  
  151. /* Flush the buffer */
  152. private int cf_encode_1d(P4(stream_CFE_state *, const byte *,
  153.   stream_cursor_write *, uint));
  154. private int cf_encode_2d(P5(stream_CFE_state *, const byte *,
  155.   stream_cursor_write *, uint, const byte *));
  156. private int
  157. s_CFE_process(stream_state *st, stream_cursor_read *pr,
  158.   stream_cursor_write *pw, bool last)
  159. {    const byte *rlimit = pr->limit;
  160.     byte *wlimit = pw->limit;
  161.     int raster = ss->raster;
  162.     int initial_count = raster << 3;
  163.     int end_count = -ss->Columns & 7;
  164.     byte end_mask = 1 << (-ss->Columns & 7);
  165.     int status = 0;
  166.     hce_declare_state;
  167.  
  168.     hce_load_state();
  169.     while ( pr->ptr < rlimit || ss->count != initial_count )
  170.     {    byte *end = ss->lbuf + raster - 1;
  171.         if_debug7('w', "[w]CFE: copy_count = %d, pr = 0x%lx(%d)0x%lx, pw = 0x%lx(%d)0x%lx\n",
  172.               ss->copy_count, (ulong)pr->ptr,
  173.               (int)(rlimit - pr->ptr), (ulong)rlimit,
  174.               (ulong)pw->ptr, (int)(wlimit - pw->ptr),
  175.               (ulong)wlimit);
  176.         /* Check whether we are still accumulating a scan line. */
  177.         if ( ss->copy_count != 0 )
  178.         {    int rcount = rlimit - pr->ptr;
  179.             int ccount = min(rcount, ss->copy_count);
  180.             memcpy(ss->lbuf + raster - ss->copy_count,
  181.                    pr->ptr + 1, ccount);
  182.             pr->ptr += ccount;
  183.             if ( (ss->copy_count -= ccount) != 0 )
  184.               goto out;
  185.             /*
  186.              * Ensure that the scan line ends with two
  187.              * polarity changes. 
  188.              */
  189.             { byte end_bit = *end & end_mask;
  190.               byte not_bit = end_bit ^ end_mask;
  191.               *end &= -end_mask;
  192.               if ( end_mask == 1 )
  193.                 end[1] = (end_bit ? 0x40 : 0x80);
  194.               else if ( end_mask == 2 )
  195.                 *end |= not_bit >> 1, end[1] = end_bit << 7;
  196.               else
  197.                 *end |= (not_bit >> 1) | (end_bit >> 2);
  198.             }
  199.         }
  200.         if ( ss->new_line )
  201.         {    /* Start a new scan line. */
  202.             byte *q = pw->ptr;
  203.             if ( wlimit - q < ss->max_line_bytes )
  204.             {    status = 1;
  205.                 break;
  206.             }
  207. #ifdef DEBUG
  208.             if ( ss->K > 0 )
  209.               { if_debug1('w', "[w]new row, k_left=%d\n",
  210.                       ss->k_left);
  211.               }
  212.             else
  213.               { if_debug0('w', "[w]new row\n");
  214.               }
  215. #endif
  216.             if ( ss->EndOfLine )
  217.             {    const cfe_run *rp =
  218.                   (ss->K <= 0 ? &cf_run_eol :
  219.                    ss->k_left > 1 ? &cf2_run_eol_2d :
  220.                    &cf2_run_eol_1d);
  221.                 cfe_run run;
  222.                 if ( ss->EncodedByteAlign )
  223.                   {    run = *rp;
  224.                     /* Pad the run on the left */
  225.                     /* so it winds up byte-aligned. */
  226.                     run.code_length +=
  227.                      (bits_left - run_eol_code_length) & 7;
  228.                     if ( run.code_length > 16 ) /* <= 23 */
  229.                       bits_left -= run.code_length & 7,
  230.                       run.code_length = 16;
  231.                     rp = &run;
  232.                   }
  233.                 hc_put_code(ss, q, rp);
  234.                 pw->ptr = q;
  235.             }
  236.             else if ( ss->EncodedByteAlign )
  237.               bits_left &= ~7;
  238.             ss->run_color = 0;
  239.             ss->new_line = false;
  240.         }
  241.         hce_store_state();
  242.         if ( ss->K > 0 )
  243.         {    /* Group 3, mixed encoding */
  244.             if ( --(ss->k_left) )    /* Use 2-D encoding */
  245.             {    status = cf_encode_2d(ss, ss->lbuf, pw, end_count, ss->lprev);
  246.                 if ( status )
  247.                   {    /* We didn't finish encoding */
  248.                     /* the line, so back out. */
  249.                     ss->k_left++;
  250.                   }
  251.             }
  252.             else    /* Use 1-D encoding */
  253.             {    status = cf_encode_1d(ss, ss->lbuf, pw, end_count);
  254.                 if ( status )
  255.                   {    /* Didn't finish encoding the line, */
  256.                     /* back out. */
  257.                     ss->k_left++;
  258.                   }
  259.                 else
  260.                   ss->k_left = ss->K;
  261.             }
  262.         }
  263.         else    /* Uniform encoding */
  264.         {    status = (ss->K == 0 ?
  265.                 cf_encode_1d(ss, ss->lbuf, pw, end_count) :
  266.                 cf_encode_2d(ss, ss->lbuf, pw, end_count, ss->lprev));
  267.         }
  268.         hce_load_state();
  269.         if ( status )
  270.           break;
  271.         if ( ss->count == end_count )
  272.         {    /* Finished a scan line, start a new one. */
  273.             ss->count = initial_count;
  274.             ss->new_line = true;
  275.             if ( ss->K != 0 )
  276.             {    byte *temp = ss->lbuf;
  277.                 ss->lbuf = ss->lprev;
  278.                 ss->lprev = temp;
  279.             }
  280.             ss->copy_count = raster;
  281.         }
  282.     }
  283.     /* Check for end of data. */
  284.     if ( last && status == 0 )
  285.     {    const cfe_run *rp =
  286.           (ss->K > 0 ? &cf2_run_eol_1d : &cf_run_eol);
  287.         int i = (!ss->EndOfBlock ? 0 : ss->K < 0 ? 2 : 6);
  288.         uint bits_to_write =
  289.           hc_bits_size - bits_left + i * rp->code_length;
  290.         byte *q = pw->ptr;
  291.         if ( wlimit - q < (bits_to_write + 7) >> 3 )
  292.         {    status = 1;
  293.             goto out;
  294.         }
  295.         if ( ss->EncodedByteAlign )
  296.           bits_left &= ~7;
  297.         while ( --i >= 0 )
  298.           hc_put_code(ss, q, rp);
  299.         /* Force out the last byte or bytes. */
  300.         pw->ptr = q = hc_put_last_bits((stream_hc_state *)ss, q);
  301.         goto ns;
  302.     }
  303. out:    hce_store_state();
  304. ns:    if_debug9('w', "[w]CFE exit %d: count = %d, run_color = %d,\n     pr = 0x%lx(%d)0x%lx; pw = 0x%lx(%d)0x%lx\n",
  305.           status, ss->count, ss->run_color,
  306.           (ulong)pr->ptr, (int)(rlimit - pr->ptr), (ulong)rlimit,
  307.           (ulong)pw->ptr, (int)(wlimit - pw->ptr), (ulong)wlimit);
  308. #ifdef DEBUG
  309.     if ( pr->ptr > rlimit || pw->ptr > wlimit )
  310.     {    lprintf("Pointer overrun!\n");
  311.         status = ERRC;
  312.     }
  313.     if ( gs_debug_c('w') && status == 1 )
  314.       {    int ti;
  315.         for ( ti = 0; ti < 2; ti++ )
  316.           {    int i;
  317.             ulong total;
  318.             dprintf1("[w]runs[%d]", ti);
  319.             for ( i = 0, total = 0; i < 41; i++ )
  320.               dprintf1(" %lu", runs_1d[ti].make_up[i]),
  321.               total += runs_1d[ti].make_up[i];
  322.             dprintf1(" total=%lu\n\t", total);
  323.             for ( i = 0, total = 0; i < 64; i++ )
  324.               dprintf1(" %lu", runs_1d[ti].termination[i]),
  325.               total += runs_1d[ti].termination[i];
  326.             dprintf1(" total=%lu\n", total);
  327.           }
  328.       }
  329. #endif
  330.     return status;
  331. }
  332.  
  333. #undef ss
  334.  
  335. /*
  336.  * For all encoding methods, we know we have a full scan line of input,
  337.  * but we must be prepared to suspend if we run out of space to store
  338.  * the output.
  339.  */
  340.  
  341. /* Encode a 1-D scan line. */
  342. private int
  343. cf_encode_1d(stream_CFE_state *ss, const byte *lbuf,
  344.   stream_cursor_write *pw, uint end_count)
  345. {    uint count = ss->count;
  346.     byte *q = pw->ptr;
  347.     byte *wlimit = pw->limit;
  348.     int rlen;
  349.     int status = 0;
  350.     hce_declare_state;
  351.  
  352.     { register const byte *p = lbuf + ss->raster - ((count + 7) >> 3);
  353.       byte invert = (ss->BlackIs1 ? 0 : 0xff);
  354.       /* Invariant: data = p[-1] ^ invert. */
  355.       register uint data = *p++ ^ invert;
  356.  
  357.       hce_load_state();
  358.       while ( count != end_count )
  359.         {    /* Parse a white run. */
  360.         cf_ensure_put_runs(max_run2_bytes, 0, out);
  361.         skip_white_pixels(data, p, count, invert, rlen);
  362.         cf_put_white_run(ss, rlen);
  363.         if ( count == end_count )
  364.           break;
  365.         /* Parse a black run. */
  366.         skip_black_pixels(data, p, count, invert, rlen);
  367.         cf_put_black_run(ss, rlen);
  368.         }
  369.     }
  370.  
  371. out:    hce_store_state();
  372.     pw->ptr = q;
  373.     ss->count = count;
  374.     return status;
  375. }
  376.  
  377. /* Encode a 2-D scan line. */
  378. private int
  379. cf_encode_2d(stream_CFE_state *ss, const byte *lbuf,
  380.   stream_cursor_write *pw, uint end_count, const byte *lprev)
  381. {    byte invert_white = (ss->BlackIs1 ? 0 : 0xff);
  382.     byte invert = (ss->run_color ? ~invert_white : invert_white);
  383.     register uint count = ss->count;
  384.     const byte *p = lbuf + ss->raster - ((count + 7) >> 3);
  385.     byte *q = pw->ptr;
  386.     byte *wlimit = pw->limit;
  387.     register uint data = *p++ ^ invert;
  388.     int status = 0;
  389.     hce_declare_state;
  390.     /* In order to handle the nominal 'changing white' at the */
  391.     /* beginning of each scan line, we need to suppress the test for */
  392.     /* an initial black bit in the reference line when we are at */
  393.     /* the very beginning of the scan line.  To avoid an extra test, */
  394.     /* we use two different mask tables. */
  395.     static const byte initial_count_bit[8] =
  396.       { 0, 1, 2, 4, 8, 0x10, 0x20, 0x40 };
  397.     static const byte further_count_bit[8] =
  398.       { 0x80, 1, 2, 4, 8, 0x10, 0x20, 0x40 };
  399.     const byte _ds *count_bit =
  400.       (count == ss->raster << 3 ? initial_count_bit : further_count_bit);
  401.  
  402.     hce_load_state();
  403.     while ( count != end_count )
  404.     {    /* If invert == invert_white, white and black have their */
  405.         /* correct meanings; if invert == ~invert_white, */
  406.         /* black and white are interchanged. */
  407.         uint a0 = count;
  408.         uint a1;
  409. #define b1 (a1 - diff)        /* only for printing */
  410.         int diff;
  411.         uint prev_count = count;
  412.         const byte *prev_p = p - lbuf + lprev;
  413.         byte prev_data = prev_p[-1] ^ invert;
  414.         int rlen;
  415.  
  416.         /* Make sure we have room for a run_horizontal plus */
  417.         /* two data runs. */
  418.         cf_ensure_put_runs(max_run3_bytes, invert != invert_white, out);
  419.         /* Find the a1 and b1 transitions. */
  420.         skip_white_pixels(data, p, count, invert, rlen);
  421.         a1 = count;
  422.         if ( (prev_data & count_bit[prev_count & 7]) )
  423.         {    /* Look for changing white first. */
  424.             skip_black_pixels(prev_data, prev_p, prev_count, invert, rlen);
  425.         }
  426.         count_bit = further_count_bit;    /* no longer at beginning */
  427. pass:        if ( prev_count != end_count )
  428.         {    skip_white_pixels(prev_data, prev_p, prev_count, invert, rlen);
  429.         }
  430.         diff = a1 - prev_count;    /* i.e., logical b1 - a1 */
  431.         /* In all the comparisons below, remember that count */
  432.         /* runs downward, not upward, so the comparisons are */
  433.         /* reversed. */
  434.         if ( diff <= -2 )
  435.         {    /* Could be a pass mode.  Find b2. */
  436.             if ( prev_count != end_count )
  437.             {    skip_black_pixels(prev_data, prev_p,
  438.                          prev_count, invert, rlen);
  439.             }
  440.             if ( prev_count > a1 )
  441.             {    /* Use pass mode. */
  442.                 if_debug4('W', "[W]pass: count = %d, a1 = %d, b1 = %d, new count = %d\n",
  443.                       a0, a1, b1, prev_count);
  444.                 hc_put_value(ss, q, cf2_run_pass_value,
  445.                          cf2_run_pass_length);
  446.                 cf_ensure_put_runs(max_run3_bytes,
  447.                            invert != invert_white,
  448.                            pass_out);
  449.                 a0 = prev_count;
  450.                 goto pass;
  451. pass_out:            count = prev_count;
  452.                 break;
  453.             }
  454.         }
  455.         /* Check for vertical coding. */
  456.         if ( diff <= 3 && diff >= -3 )
  457.         {    /* Use vertical coding. */
  458.             const cfe_run *cp;
  459.             if_debug5('W', "[W]vertical %d: count = %d, a1 = %d, b1 = %d, new count = %d\n",
  460.                   diff, a0, a1, b1, count);
  461.             cp = &cf2_run_vertical[diff + 3];
  462.             hc_put_code(ss, q, cp);
  463.             invert = ~invert;    /* a1 polarity changes */
  464.             data ^= 0xff;
  465.             continue;
  466.         }
  467.         /* No luck, use horizontal coding. */
  468.         if ( count != end_count )
  469.         {    skip_black_pixels(data, p, count, invert, rlen);    /* find a2 */
  470.         }
  471.         hc_put_value(ss, q, cf2_run_horizontal_value,
  472.                  cf2_run_horizontal_length);
  473.         a0 -= a1;
  474.         a1 -= count;
  475.         if ( invert == invert_white )
  476.         {    if_debug3('W', "[W]horizontal: white = %d, black = %d, new count = %d\n",
  477.                   a0, a1, count);
  478.             cf_put_white_run(ss, a0);
  479.             cf_put_black_run(ss, a1);
  480.         }
  481.         else
  482.         {    if_debug3('W', "[W]horizontal: black = %d, white = %d, new count = %d\n",
  483.                   a0, a1, count);
  484.             cf_put_black_run(ss, a0);
  485.             cf_put_white_run(ss, a1);
  486. #undef b1
  487.         }
  488.     }
  489. out:    hce_store_state();
  490.     pw->ptr = q;
  491.     ss->count = count;
  492.     return status;
  493. }
  494.  
  495. /* Stream template */
  496. const stream_template s_CFE_template =
  497. {    &st_CFE_state, s_CFE_init, s_CFE_process,
  498.     2, 15, /* 31 left-over bits + 7 bits of padding + 6 13-bit EOLs */
  499.     s_CFE_release, s_CFE_set_defaults
  500. };
  501.